//给定二叉搜索树（BST）的根节点 root 和一个整数值 val。 
//
// 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：root = [4,2,7,1,3], val = 2
//输出：[2,1,3]
// 
//
// Example 2: 
//
// 
//输入：root = [4,2,7,1,3], val = 5
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 数中节点数在 [1, 5000] 范围内 
// 1 <= Node.val <= 10⁷ 
// root 是二叉搜索树 
// 1 <= val <= 10⁷ 
// 
// Related Topics 树 二叉搜索树 二叉树 👍 261 👎 0

package leetcode.editor.cn;

class SearchInABinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new SearchInABinarySearchTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        /**
         * 递归法
         *
         * @param root
         * @param val
         * @return
         */
//        public TreeNode searchBST(TreeNode root, int val) {
//            // 找到值以后，停止递归
//            if (root == null || root.val == val) {
//                return root;
//            }
//
//            // 根据二叉搜索树的规律进行递归，注意使用了return，因为找到了就返回，不需要遍历整颗树
//            if (root.val > val) return searchBST(root.left, val);
//            if (root.val < val) return searchBST(root.right, val);
//
//            // 没有找到
//            return null;
//        }

        /**
         * 递归法
         *
         * @param root
         * @param val
         * @return
         */
        /*public TreeNode searchBST(TreeNode root, int val) {
            // 由于二叉搜索树已经确认了迭代的方向，所以不需要栈也不需要回溯
            while (root != null) {
                if (root.val > val) root = root.left;
                else if (root.val < val) root = root.right;
                else return root;
            }

            return null;
        }*/

        // 递归法
        /*public TreeNode searchBST(TreeNode root, int val) {
            if (root == null && root.val == val) return root;
            if (root.val > val) return searchBST(root.left, val);
            if (root.val < val) return searchBST(root.right, val);
            return null;
        }*/
        /*public TreeNode searchBST(TreeNode root, int val) {
            while (root != null) {
                if (root.val < val) root = root.right;
                else if (root.val > val) root = root.left;
                else return root;
            }
            return null;
        }*/

        public TreeNode searchBST(TreeNode root, int val) {
            traversal(root, val);
            return node;
        }

        TreeNode node;

        private void traversal(TreeNode root, int val) {
            if (root == null) {
                return;
            }

            if (val < root.val) {
                searchBST(root.left, val);
            }

            if (val > root.val) {
                searchBST(root.right, val);
            }

            if (val == root.val) node = root;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
